package leetcode_1801_1900;

import java.util.Arrays;

public class LeeCode_1824 {
    public static void main(String[] args) {
        System.out.println(minSideJumps(new int[]{0, 1, 2, 3, 0}));
        System.out.println(minSideJumps(new int[]{0, 1, 1, 3, 3, 0}));
        System.out.println(minSideJumps(new int[]{0, 2, 1, 0, 3, 0}));
    }
    private static int minSideJumps(int[] obstacles) {
        int n = obstacles.length;
        int[][] next = new int[3][n];
        for (int i = 0; i < 3; i++) {
            next[i][n - 1] = n;
        }
        for(int j = n - 2; j >= 0 ; j--){
            if (obstacles[j] == 0) {
                for (int i = 0; i < 3; i++) {
                    next[i][j] = next[i][j + 1];
                }
                continue;
            }
            int index = obstacles[j] - 1;
            next[index][j] = j;
            for (int i = 0; i < 3; i++) {
                if (i == index)
                    continue;
                next[i][j] = next[i][j + 1];
            }
        }
        int j = 0, i = 1, ans = 0;
        while (next[i][j] != n){
            j = next[i][j] - 1;
            int max = 0, index = 0;
            for (int k = 0; k < 3; k++) {
                if (next[k][j] > max){
                    max = next[k][j];
                    index = k;
                }
            }
            i = index;
            ans++;
        }
        return ans;
    }
}
